package linkList;

public class MyLinkList<T> {
    private int num = 0;
    private Node first = null;
    private Node last = null;

    public int getNum() {
        return num;
    }

    public void add(int index , T date){
        Node newNode = new Node(date);
        if (num == 0){
            first = newNode;
            last = newNode;
            num++;
            return;
        }
        if (index < 0 || index > num){
            throw new RuntimeException("下标越界");
        }

        if (index == 0){
            newNode.right = first;
            first.left = newNode;
            first = newNode;
            num++;
            return;
        }
        if (index == num){
            newNode.left = last;
            last.right = newNode;
            last = newNode;
            num++;
            return;
        }
        Node hello = findNode(index);
        Node hi = hello.left;

        newNode.right = hello;
        newNode.left = hi;
        hello.left = newNode;
        hi.right = newNode;
        num++;

    }
    public T remove(int index){

        Node node = findNode(index);

        if (index < 0 || index >= num){
            throw new RuntimeException("下标越界");
        }
        if (num == 1 ){
            last = null;
            first = null;
            num--;
            return (T)node.date;
        }
        if (index == 0){
            first = first.right;
            num--;
            return (T)node.date;
        }
        if (index == num-1){
            last =last.left;
            num--;
            return (T)node.date;
        }

        Node nodeLeft = node.left;
        Node nodeRight = node.right;
        nodeLeft.right = nodeRight;
        nodeRight.left = nodeLeft;
        num--;

        return (T)node.date;
    }

    public T find(int index){
        if (index > (num>>1) ){
            return findByRight(index);
        }
        return findByLeft(index);
    }


    private T findByLeft(int index){
        Node node = first;
        for (int i = 0 ; i < index ; i++){
            node = node.right;
        }
        return (T)node.date;
    }

    private T findByRight(int index){
        Node node = last;
        for (int i = num-1 ; i > index ; i--){
            node = node.left;
        }
        return (T)node.date;
    }



    private Node findNode(int index){
        Node now = first;
        for (int i = 0 ; i < index ; i++){
            now = now.right;
        }
        return now;
    }
}
